package com.cat.dynamicPlanning02;

import java.util.Arrays;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/number-of-ways-to-wear-different-hats-to-each-other/description/
 * @create 2025/10/14 20:45
 * @since JDK17
 */

public class Solution20 {
    int[] h;
    int N = ((int) (1e9 + 7)), n, m;
    int[][] dp;
    int dfs(int i, int p) {
        if (p == (1 << n) - 1) {    // 所有的人都被满足了
            return 1;
        }
        if (i == m + 1) {
            return 0;
        }
        if (dp[p][i] != -1) {
            return dp[p][i];
        }
        int ans = dfs(i + 1, p);    // 不用当前这顶帽子
        int cur = h[i]; // 帽子
        for (int j = 0; j < n; j++) {   //
            if ((cur >> j & 1) != 0 && (p >> j & 1) == 0) {  // 该帽子可以满足j人
                ans = (ans + dfs(i + 1, p | (1 << j))) % N;
            }
        }
        return dp[p][i] = ans;
    }

    public int numberWays(List<List<Integer>> hats) {
        n = hats.size();
        for (var people : hats) {
            for (var hat : people) {
                m = Math.max(m, hat);
            }
        }
        h = new int[m + 1];
        for (int i = 0; i < n; i++) {
            for (int hat : hats.get(i)) {
                h[hat] |= 1 << i;   // 这个帽子可以满足第i号人
            }
        }
        dp = new int[1 << n][m + 1];
        for (int i = 0; i < 1 << n; i++) {
            Arrays.fill(dp[i], -1);
        }
        return dfs(1, 0);
    }
}
